import java.util.Arrays;


public class DAY3_2 {
    public int MoreThanHalfNum_Solution1(int[] array) {
        if(array==null||array.length==0){
            return 0;
        }
        Arrays.sort(array);
        int len=array.length;
        int midNum=array[len/2];
        int count=0;
        for (int i = 0; i < len; i++) {
            if(array[i]==midNum){
                count++;
            }
        }
        if(count>len/2){
            return midNum;
        }
        return 0;
    }



    public static int MoreThanHalfNum_Solution2(int[] array) {
        if(array==null||array.length==0){
            return 0;
        }
        int result =array[0];
        int times=1;
        for (int i = 1; i < array.length; ++i) {
            if(times!=0){
                if(array[i]==result){
                    ++times;
                }else{
                    --times;
                }
            }else{
                result=array[i];
                times=1;
            }
        }
        times=0;
        for (int i = 0; i < array.length; ++i) {
            if(array[i]==result)++times;
        }
        return (times>array.length/2)?result:0;

    }

    public static void main(String[] args) {
        int[] array={1,2,3,2,2,2,2,3,4,5};
        int a=MoreThanHalfNum_Solution2(array);
        System.out.println(a);
    }
}
